ICPC Live Archive/3928 - Ballroom lights/help/gomox.ar-pap-2010-d9b17e5cb110/tpc/billing-tables/main.cpp

   1 #include <string>
   2 #include <map>
   3 #include <set>
   4 #include <vector>
   5 #include <stack>
   6 #include <iostream>
   7 #include <sstream>
   8 #include <iomanip>
   9 #include <cassert>
  10 #include <cstdlib>
  11 #include <stdio.h>
  12
  13 using namespace std;
  14
  15 #define forsn(i, s, n)  for (int i = (s); i < (n); i++)
  16 #define forn(i, n)      forsn (i, 0, n)
  17 #define dforn(i, n)     for (int i = (n); i-- > 0;)
  18
  19 #define ALPHA_SIZE      10
  20 #define ALPHA_VAL(C)    ((C) - '0')
  21 #define foralpha(x)     forn (x, ALPHA_SIZE)
  22
  23 typedef unsigned long long int lluint;
  24
  25 typedef const string *Value;
  26
  27 string itos(lluint i, int width) {
  28         if (width == 0) return "";
  29         ostringstream os;
  30         os << setw(width) << setfill('0') << i;
  31         return os.str();
  32 }
  33
  34 /**** String register ****/
  35
  36 set<string> _reg;
  37
  38 Value reg_intern(const string& s) {
  39         return &*_reg.insert(s).first;
  40 }
  41
  42 void reg_free() {
  43         _reg = set<string>();
  44 }
  45
  46 /**** Trie ****/
  47
  48 struct Node {
  49         Node *children[ALPHA_SIZE];
  50         Value value;
  51 };
  52
  53 typedef Node *Trie;
  54 #define trie_new()      NULL
  55 #define Empty           NULL
  56
  57 void trie_free(Trie tr) {
  58         if (!tr) return;
  59         foralpha (dig) {
  60                 trie_free(tr->children[dig]);
  61         }
  62         delete tr;
  63 }
  64
  65 void _trie_delete_children(Trie tr) {
  66         foralpha (dig) if (tr->children[dig]) {
  67                 trie_free(tr->children[dig]);
  68                 tr->children[dig] = NULL;
  69         }
  70 }
  71
  72 void _trie_collapse_children(Trie tr) {
  73         if (!tr->children[0] || tr->children[0]->value == Empty) return;
  74         foralpha (dig) {
  75                 if (!tr->children[dig]) return;
  76                 if (tr->children[dig]->value != tr->children[0]->value) return;
  77         }
  78
  79         tr->value = tr->children[0]->value;
  80         _trie_delete_children(tr);
  81 }
  82
  83 // invariante: los valores estan en las hojas
  84 void trie_add(Trie *tr, const char *s, Value v) {
  85         if (*tr == NULL) {
  86                 *tr = new Node();
  87                 foralpha (dig) (*tr)->children[dig] = NULL;
  88                 (*tr)->value = Empty;
  89         }
  90         if (!*s) {
  91                 (*tr)->value = v;
  92                 _trie_delete_children(*tr);
  93         } else {
  94                 if ((*tr)->value != Empty) {
  95                         foralpha (dig) {
  96                                 trie_add(&(*tr)->children[dig], "", (*tr)->value);
  97                         }
  98                         (*tr)->value = Empty;
  99                 }
 100                 trie_add(&(*tr)->children[ALPHA_VAL(*s)], &s[1], v);
 101
 102                 _trie_collapse_children(*tr);
 103         }
 104 }
 105
 106 bool trie_has_children(Trie tr) {
 107         foralpha (dig) {
 108                 if (tr->children[dig] == NULL) continue;
 109                 return true;
 110         }
 111         return false;
 112 }
 113
 114 void trie_debug(Trie tr, int depth) {
 115         if (!tr) return;
 116         foralpha (dig) {
 117                 if (!tr->children[dig]) continue;
 118                 forn (i, depth) { cout << " "; }
 119                 cout << itos(dig, 1);
 120                 if (tr->children[dig]->value) {
 121                         cout << "  (" << *(tr->children[dig]->value) << ")";
 122                 }
 123                 cout << endl;
 124                 trie_debug(tr->children[dig], depth + 1);
 125         }
 126 }
 127
 128 /**** Resultado ****/
 129
 130 typedef pair<string, Value> ResultItem;
 131 vector<ResultItem> result;
 132 Value Invalid;
 133
 134 #define _produce(S, V)          if ((V) != Invalid) { result.push_back(ResultItem((S), (V))); }
 135 #define Maxlen 20
 136 char prefix_buf[Maxlen];
 137 void _build_result_rec(Trie tr, int prefix_length) {
 138         if (tr == NULL) return;
 139         if (!trie_has_children(tr)) {
 140                 // no children
 141                 prefix_buf[prefix_length] = '\0';
 142                 _produce(string(prefix_buf), tr->value);
 143         } else {
 144                 // visit the children
 145                 foralpha (dig) {
 146                         prefix_buf[prefix_length] = '0' + dig;
 147                         _build_result_rec(tr->children[dig], prefix_length + 1);
 148                 }
 149         }
 150 }
 151
 152 void trie_print_result(Trie tr) {
 153         Invalid = reg_intern("invalid");
 154         result = vector<ResultItem>();
 155
 156         if (!trie_has_children(tr) && tr->value != Empty && tr->value != Invalid) {
 157                 // special case: every prefix has the same type
 158                 printf("%d\n",ALPHA_SIZE);
 159                 foralpha (dig) {
 160                         printf("%d %s\n",dig,(*tr->value).c_str());
 161                 }
 162         } else {
 163                 _build_result_rec(tr, 0);
 164
 165                 printf("%d\n",result.size());
 166                 forn (i, (int)result.size()) {
 167                         printf("%s %s\n",result[i].first.c_str(),(*result[i].second).c_str());
 168                 }
 169         }
 170 }
 171
 172 /**** Intervalos ****/
 173
 174 #define IMP(X, Y)       (!(X) || (Y))
 175 void add_interval(Trie *tr, int pref_size, lluint from, lluint to, Value val) {
 176         lluint pot = 1;
 177         forn (t, 2) {
 178                 lluint *from_to = (t == 0 ? &from : &to);
 179                 while (pot > 0 && IMP(t == 0, from + pot <= to)) {
 180                         while (from + pot <= to && *from_to % (pot * 10) > 0) {
 181                                 string element(itos(from / pot, pref_size));
 182                                 trie_add(tr, element.c_str(), val);
 183                                 from += pot;
 184                         }
 185                         if (t == 0) {
 186                                 pot *= 10;
 187                                 pref_size--;
 188                         } else {
 189                                 pot /= 10;
 190                                 pref_size++;
 191                         }
 192                 }
 193                 if (t == 1) break;
 194                 while (from + pot > to) { pot /= 10; pref_size++; }
 195         }
 196 }
 197
 198 lluint atoll_(string s) {
 199         lluint r = 0;
 200         forn (i, s.size()) {
 201                 r = 10 * r + ALPHA_VAL(s[i]);
 202         }
 203         return r;
 204 }
 205
 206 /**** Main ****/
 207
 208 struct InputItem {
 209         int pref_size;
 210         lluint from, to;
 211         Value name_id;
 212 };
 213 int main() {
 214         bool primero = true;
 215         while (true) {
 216                 int nlines;
 217                 cin >> nlines;
 218                 if (cin.eof()) break;
 219
 220                 if (primero) {
 221                         primero = false;
 222                 } else {
 223                         printf("\n");
 224                 }
 225
 226                 vector<InputItem> todo_list;
 227
 228                 // Read the lines and build the todo list
 229                 forn (line, nlines) {
 230                         string from, sep, to, name;
 231                         cin >> from >> sep >> to >> name;
 232
 233                         int k = from.size() - to.size();
 234                         InputItem item;
 235                         item.name_id = reg_intern(name);
 236                         item.from = atoll_(from);
 237                         item.to = atoll_(from.substr(0, k) + to) + 1;
 238                         item.pref_size = from.size();
 239
 240                         todo_list.push_back(item);
 241                 }
 242
 243                 // Process the lines in reverse order
 244                 Trie tr = trie_new();
 245                 dforn (i, nlines) {
 246                         InputItem& item(todo_list[i]);
 247                         add_interval(&tr, item.pref_size, item.from, item.to, item.name_id);
 248                 }
 249
 250                 trie_print_result(tr);
 251                 trie_free(tr);
 252                 reg_free();
 253         }
 254
 255         return 0;
 256 }